% Ejercicio "Listas en PROLOG en forma canónica"
\subsection*{\fbox{\theejercicio} - Listas en PROLOG en forma can\'onica}

La siguiente gram\'atica corresponde a la fase sint\'actica del an\'alisis de algunas listas v\'alidas en PROLOG:

\begin{center}
\begin{tabular}{|lcl|} \hline
                &               &                             \\
{\em Lista}     & $\rightarrow$ & [ ]                         \\
{\em Lista}     & $\rightarrow$ & [ {\em T\'ermino} ]         \\
{\em T\'ermino} & $\rightarrow$ & {\em T\'ermino , T\'ermino} \\
{\em T\'ermino} & $\rightarrow$ & {\bf \'ATOMO}               \\
{\em T\'ermino} & $\rightarrow$ & {\bf VARIABLE}              \\
{\em T\'ermino} & $\rightarrow$ & {\em Lista}                 \\
                &               &                             \\ \hline
\end{tabular}
\end{center}

En donde los {\bf \'ATOMOS} son secuencias de caracteres alfanum\'ericos que comienzan por una letra min\'uscula, y las {\bf VARIABLES} son secuencias de car\'acteres que comienzan por una letra may\'uscula. A todos los efectos se considera el car\'acter subrayado como una letra may\'uscula.

La gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
             &               &                     \\
{\em Lista}  & $\rightarrow$ & [ ]                 \\
{\em Lista}  & $\rightarrow$ & [ Cabeza $|$ Cola ] \\
{\em Cabeza} & $\rightarrow$ & {\em Lista}         \\
{\em Cabeza} & $\rightarrow$ & {\bf \'ATOMO}       \\
{\em Cabeza} & $\rightarrow$ & {\bf VARIABLE}      \\
{\em Cola}   & $\rightarrow$ & {\em Lista}         \\
             &               &                     \\ \hline
\end{tabular}
\end{center}

genera listas v\'alidas en PROLOG escritas en forma can\'onica. Cualquier lista PROLOG, puede traducirse a su correspondiente lista can\'onica considerando que su primer {\em T\'ermino} corresponde a la {\em Cabeza} de la lista can\'onica y la {\em Cola} est\'a formada por la lista compuesta por los dem\'as elementos.

\smallskip

Ejemplos:

\begin{center}
\begin{tabular}{ll}
Listas               & Listas can\'onicas            \\
\verb@[a1]@          & \verb@[a1|[]]@                \\
\verb@[a1,a2]@       & \verb@[a1|[a2|[]]]@           \\
\verb@[[a1,a2],a3]@  & \verb@[[a1|[a2|[]]]|[a3|[]]]@ \\
\end{tabular}
\end{center}

Construir mediante LEX y YACC un traductor que convierta cualquier lista PROLOG generada por la primera gram\'atica en su correspondiente lista can\'onica generada por esta segunda gram\'atica.

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

